using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ImryStefanGAnamespace
{
    public class GeneticAlgorithmClass
    {
        public static CVRPSolution GeneticAlgorithm(Stopwatch stopWatch)
        {
            List<CVRPSolution> currentPopulation = new List<CVRPSolution>();

            int totalPopulationCount = GenerateNewPopulation(currentPopulation, stopWatch);

            // Sort by fitness
            currentPopulation.Sort();

            Console.WriteLine("Starting best solution:");
            currentPopulation.Last().FeasibilityCheck();
            double bestCost = currentPopulation.Last().TotalCost();
            double bestInfeasCost = currentPopulation.Last().TotalCost();
            CVRPSolution bestSolution = currentPopulation.Last().Clone();

            double startTimeOfLoop = stopWatch.Elapsed.TotalSeconds;
            int generation = 0;
            while (stopWatch.Elapsed.TotalSeconds < Program.totalTime)
            {
                generation++;
                currentPopulation.RemoveRange(0, totalPopulationCount / 2);

                // Create children
                for (int i = 0; i < totalPopulationCount / 2; i++)
                {
                    int mommy = Program.rand.Next(totalPopulationCount / 2);
                    int daddy = Program.rand.Next(totalPopulationCount / 2 - 1);
                    if (mommy <= daddy) daddy++;

                    CVRPSolution child = Reproduce(currentPopulation[mommy], currentPopulation[daddy]);

                    currentPopulation.Add(child);
                    
                    if (child.TotalCost() < bestCost - 0.00000001)
                    {
                        Console.WriteLine("New best feasible answer! " + currentPopulation.Last().TotalCost());
                        bestCost = currentPopulation.Last().TotalCost();
                        bestSolution = child.Clone();
                    }
                }

                // Sort by total cost
                currentPopulation.Sort();

                if (currentPopulation.Last().TotalCost() < bestInfeasCost - 0.00000001 && currentPopulation.Last().TotalCost() < bestCost - 0.00000001)
                {
                    bestInfeasCost = currentPopulation.Last().TotalCost();
                    Console.WriteLine("bestInfeasCost " +bestInfeasCost);
                }
            }
            double averageTime = (stopWatch.Elapsed.TotalSeconds - startTimeOfLoop) / generation;
            Console.WriteLine("Generations: " + generation + ". Seconds per generation: " + averageTime);
            return bestSolution;
        }

        private static int GenerateNewPopulation(List<CVRPSolution> currentPopulation, Stopwatch stopWatch)
        {
            int totalPopulationSize=0;
            do
            {
                currentPopulation.Add(SavingsClass.RandomizedSavingsMethod());
                totalPopulationSize++;
            } while (totalPopulationSize % 4 != 0 || (totalPopulationSize < Program.maxPopulation && stopWatch.Elapsed.TotalSeconds < Program.totalTime/5));
            Console.WriteLine("totalPopulationSize: " + totalPopulationSize + ". Seconds to generate: " + stopWatch.Elapsed.TotalSeconds);
            return totalPopulationSize;
        }

        private static CVRPSolution Reproduce(CVRPSolution cVRPSolution1, CVRPSolution cVRPSolution2)
        {

            // We first find all of the segments which appear in both solutions
            int[] overlappingIndicator = new int[Program.vrpData.Dimension];
            List<Segment> overlappingSegments = FindOverlappingSegments(cVRPSolution1, cVRPSolution2, overlappingIndicator);
            
            BreakUpInfeasibleSegments(overlappingSegments);

            // Put all complete routes in their own list - and don't mess with them
            List<Segment> completeRoutes = new List<Segment>();

            for (int i = 0; i < overlappingSegments.Count; i++)
            {
                if (overlappingSegments[i].nodesOnSegment.First() == 0 && overlappingSegments[i].nodesOnSegment.First() == overlappingSegments[i].nodesOnSegment.Last())
                {
                    completeRoutes.Add(overlappingSegments[i]);
                    overlappingSegments.RemoveAt(i);
                    i--;
                }
            }

            // If solutions are identical, mutate
            while (overlappingSegments.Count() == 0)
            {
                cVRPSolution1.RandomlyMutate();
                cVRPSolution2.RandomlyMutate();

                overlappingIndicator = new int[Program.vrpData.Dimension];
                overlappingSegments = FindOverlappingSegments(cVRPSolution1, cVRPSolution2, overlappingIndicator);

                BreakUpInfeasibleSegments(overlappingSegments);

                // Put all complete routes in their own list - and don't mess with them
                completeRoutes = new List<Segment>();

                for (int i = 0; i < overlappingSegments.Count; i++)
                {
                    if (overlappingSegments[i].nodesOnSegment.First() == 0 && overlappingSegments[i].nodesOnSegment.First() == overlappingSegments[i].nodesOnSegment.Last())
                    {
                        completeRoutes.Add(overlappingSegments[i]);
                        overlappingSegments.RemoveAt(i);
                        i--;
                    }
                }
            }

            // Join the incomplete segments.
            JoinSegments(overlappingSegments);

            // Now lets deal with the remaining nodes - which were not in the overlapping segments
            List<Segment> nonOverlappingSegments = new List<Segment>();
            CalculateNonOverlappingSegments(nonOverlappingSegments, overlappingIndicator, cVRPSolution1);
            CalculateNonOverlappingSegments(nonOverlappingSegments, overlappingIndicator, cVRPSolution2);

            // Repeat the procedure until all segments have been included in routes
            while (nonOverlappingSegments.Count > 0)
            {
                int totalElements = 0; // Needed for future - when choosing a segment at random, want a bigger one with higher probability
                for (int i = 0; i < nonOverlappingSegments.Count; i++)
                {
                    for (int okkk = 0; okkk < nonOverlappingSegments[i].nodesOnSegment.Count(); okkk++)
                    {
                        totalElements++;
                    }
                }
                // choose a segment at random
                int theRandomIndex = Program.rand.Next(totalElements);
                int currentCount = 0;
                int segmentIndex = 0;
                for (int i = 0; i < nonOverlappingSegments.Count; i++)
                {
                    currentCount += nonOverlappingSegments[i].nodesOnSegment.Count();
                    if (theRandomIndex < currentCount)
                    {
                        segmentIndex = i;
                        break;
                    }
                }

                for (int i = 0; i < nonOverlappingSegments[segmentIndex].nodesOnSegment.Count(); i++)
                {
                    if (nonOverlappingSegments[segmentIndex].nodesOnSegment[i] > 0)
                        overlappingIndicator[nonOverlappingSegments[segmentIndex].nodesOnSegment[i]] = 1;
                }

                InsertSegmentIntoCollection(nonOverlappingSegments[segmentIndex], overlappingSegments);

                nonOverlappingSegments = new List<Segment>();
                CalculateNonOverlappingSegments(nonOverlappingSegments, overlappingIndicator, cVRPSolution1);
                CalculateNonOverlappingSegments(nonOverlappingSegments, overlappingIndicator, cVRPSolution2);
            }

            CVRPSolution child = new CVRPSolution();

            for (int i = 0; i < completeRoutes.Count; i++)
                child.routesInSolution.Add(completeRoutes[i]);

            for (int i = 0; i < overlappingSegments.Count; i++)
            {
                overlappingSegments[i].Cleanup();
                child.routesInSolution.Add(overlappingSegments[i]);
            }

            return child;
        }

        private static void BreakUpInfeasibleSegments(List<Segment> overlappingSegments)
        {
            bool foundInfeasible = false;
            do
            {
                foundInfeasible = false;
                for (int i = 0; i < overlappingSegments.Count; i++)
                {
                    if (overlappingSegments[i].segmentDemand > Program.vrpData.Capacity)
                    {
                        int splittingAfterIndex = Program.rand.Next(overlappingSegments[i].nodesOnSegment.Count() - 1 - (overlappingSegments[i].nodesOnSegment.First() == 0 ? 1 : 0) - (overlappingSegments[i].nodesOnSegment.Last() == 0 ? 1 : 0)) + (overlappingSegments[i].nodesOnSegment.First() == 0 ? 1 : 0);
                        overlappingSegments.Add(new Segment());
                        for (int j = 0; j <= splittingAfterIndex; j++)
                        {
                            overlappingSegments.Last().Add(overlappingSegments[i].nodesOnSegment[j]);
                        }
                        overlappingSegments[i].RemoveNodesUpToAndIncluding(splittingAfterIndex);
                    }
                }
            } while (foundInfeasible == true);
        }

        private static void InsertSegmentIntoCollection(Segment segmentToInsert, List<Segment> overlappingSegments)
        {
            // Actually insert the whole segment. If it doesnt fit, call this function recursively
            int mergeType = -1;
            int mergeAt = -1;
            double bestMergeCost = double.MaxValue;
            int indexOfSecondSegment = -1;
            bool mergeDone = false;
            for (int j = 0; j < overlappingSegments.Count; j++)
            {
                int sumSideDepots = 0;
                if (segmentToInsert.nodesOnSegment.First() == 0)
                    sumSideDepots++;
                if (segmentToInsert.nodesOnSegment.Last() == 0)
                    sumSideDepots++;
                if (overlappingSegments[j].nodesOnSegment.First() == 0)
                    sumSideDepots++;
                if (overlappingSegments[j].nodesOnSegment.Last() == 0)
                    sumSideDepots++;

                if (sumSideDepots < 3 && segmentToInsert.segmentDemand + overlappingSegments[j].segmentDemand < Program.vrpData.Capacity)
                {
                    mergeDone = true;
                    if (segmentToInsert.nodesOnSegment.First() != 0 && overlappingSegments[j].nodesOnSegment.First() != 0 && bestMergeCost > Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), 0])
                    {
                        mergeType = 1;
                        bestMergeCost = Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), 0];
                        indexOfSecondSegment = j;
                    }
                    if (segmentToInsert.nodesOnSegment.First() != 0 && overlappingSegments[j].nodesOnSegment.Last() != 0 && bestMergeCost > Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), 0])
                    {
                        mergeType = 2;
                        bestMergeCost = Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), 0];
                        indexOfSecondSegment = j;
                    }
                    if (segmentToInsert.nodesOnSegment.Last() != 0 && overlappingSegments[j].nodesOnSegment.First() != 0 && bestMergeCost > Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), 0])
                    {
                        mergeType = 3;
                        bestMergeCost = Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), 0];
                        indexOfSecondSegment = j;
                    }
                    if (segmentToInsert.nodesOnSegment.Last() != 0 && overlappingSegments[j].nodesOnSegment.Last() != 0 && bestMergeCost > Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), 0])
                    {
                        mergeType = 4;
                        bestMergeCost = Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), 0];
                        indexOfSecondSegment = j;
                    }

                    // Might "merge" on the inside
                    if (segmentToInsert.nodesOnSegment.First() != 0 && segmentToInsert.nodesOnSegment.Last() != 0)
                    {
                        for (int k = 0; k < overlappingSegments[j].nodesOnSegment.Count; k++)
                        {
                            if (overlappingSegments[j].nodesOnSegment[k] == -1)
                            {
                                double mergeCost1 = Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment[k - 1]]
                                    + Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment[k - 1], overlappingSegments[j].nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), 0]
                                    - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), 0];
                                double mergeCost2 = Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment[k + 1]]
                                    + Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment[k - 1]]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment[k - 1], overlappingSegments[j].nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.Last(), 0]
                                    - Program.vrpData.Distances[segmentToInsert.nodesOnSegment.First(), 0];

                                if (mergeCost1 < bestMergeCost)
                                {
                                    mergeType = 5;
                                    mergeAt = k;
                                    bestMergeCost = mergeCost1;
                                    indexOfSecondSegment = j;
                                }
                                if (mergeCost2 < bestMergeCost)
                                {
                                    mergeType = 6;
                                    mergeAt = k;
                                    bestMergeCost = mergeCost2;
                                    indexOfSecondSegment = j;
                                }

                            }
                        }
                    }
                    // Might "merge" on the inside
                    if (overlappingSegments[j].nodesOnSegment.First() != 0 && overlappingSegments[j].nodesOnSegment.Last() != 0)
                    {
                        for (int k = 0; k < segmentToInsert.nodesOnSegment.Count(); k++)
                        {
                            if (segmentToInsert.nodesOnSegment[k] == -1)
                            {
                                double mergeCost1 = Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.First(), segmentToInsert.nodesOnSegment[k - 1]]
                                    + Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.Last(), segmentToInsert.nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[segmentToInsert.nodesOnSegment[k - 1], segmentToInsert.nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.Last(), 0]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.First(), 0];
                                double mergeCost2 = Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.First(), segmentToInsert.nodesOnSegment[k + 1]]
                                    + Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.Last(), segmentToInsert.nodesOnSegment[k - 1]]
                                    - Program.vrpData.Distances[segmentToInsert.nodesOnSegment[k - 1], segmentToInsert.nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.Last(), 0]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.First(), 0];

                                if (mergeCost1 < bestMergeCost)
                                {
                                    mergeType = 7;
                                    mergeAt = k;
                                    bestMergeCost = mergeCost1;
                                    indexOfSecondSegment = j;
                                }
                                if (mergeCost2 < bestMergeCost)
                                {
                                    mergeType = 8;
                                    mergeAt = k;
                                    bestMergeCost = mergeCost2;
                                    indexOfSecondSegment = j;
                                }

                            }
                        }
                    }

                }
            }
            if (mergeDone == true && mergeType != -1)
            {
                switch (mergeType)
                {
                    case 1:
                        segmentToInsert.nodesOnSegment.Reverse();
                        segmentToInsert.Add(-1);
                        segmentToInsert.AddRange(overlappingSegments[indexOfSecondSegment]);
                        overlappingSegments.RemoveAt(indexOfSecondSegment);
                        overlappingSegments.Add(segmentToInsert);
                        break;
                    case 2:
                        overlappingSegments[indexOfSecondSegment].Add(-1);
                        overlappingSegments[indexOfSecondSegment].AddRange(segmentToInsert);
                        break;
                    case 3:
                        segmentToInsert.Add(-1);
                        segmentToInsert.AddRange(overlappingSegments[indexOfSecondSegment]);
                        overlappingSegments.RemoveAt(indexOfSecondSegment);
                        overlappingSegments.Add(segmentToInsert);
                        break;
                    case 4:
                        segmentToInsert.nodesOnSegment.Reverse();
                        overlappingSegments[indexOfSecondSegment].Add(-1);
                        overlappingSegments[indexOfSecondSegment].AddRange(segmentToInsert);
                        break;
                    case 5:
                        overlappingSegments[indexOfSecondSegment].Insert(mergeAt, -1);
                        overlappingSegments[indexOfSecondSegment].InsertRange(mergeAt + 1, segmentToInsert);
                        break;
                    case 6:
                        segmentToInsert.nodesOnSegment.Reverse();
                        overlappingSegments[indexOfSecondSegment].Insert(mergeAt, -1);
                        overlappingSegments[indexOfSecondSegment].InsertRange(mergeAt + 1, segmentToInsert);
                        break;
                    case 7:
                        segmentToInsert.Insert(mergeAt, -1);
                        segmentToInsert.InsertRange(mergeAt + 1, overlappingSegments[indexOfSecondSegment]);
                        overlappingSegments.RemoveAt(indexOfSecondSegment);
                        overlappingSegments.Add(segmentToInsert);
                        break;
                    case 8:
                        overlappingSegments[indexOfSecondSegment].nodesOnSegment.Reverse();
                        segmentToInsert.Insert(mergeAt, -1);
                        segmentToInsert.InsertRange(mergeAt + 1, overlappingSegments[indexOfSecondSegment]);
                        overlappingSegments.RemoveAt(indexOfSecondSegment);
                        overlappingSegments.Add(segmentToInsert);
                        break;
                }
            }
            // Otherwise, either split, or just add it as a new route
            else if (segmentToInsert.nodesOnSegment.First() == 0)
            {
                segmentToInsert.RemoveNodesUpToAndIncluding(0);
                InsertSegmentIntoCollection(segmentToInsert, overlappingSegments);
            }
            else if (segmentToInsert.nodesOnSegment.Last() == 0)
            {
                segmentToInsert.RemoveLastNode();
                InsertSegmentIntoCollection(segmentToInsert, overlappingSegments);
            }
            else
            {
                int actualNumberOfNodes = segmentToInsert.nodesOnSegment.Count() - (segmentToInsert.nodesOnSegment.First() == 0 ? 1 : 0) - (segmentToInsert.nodesOnSegment.Last() == 0 ? 1 : 0);
                if (actualNumberOfNodes > 1)
                {
                    int splittingAfterIndex = Program.rand.Next(segmentToInsert.nodesOnSegment.Count() - 1 - (segmentToInsert.nodesOnSegment.First() == 0 ? 1 : 0) - (segmentToInsert.nodesOnSegment.Last() == 0 ? 1 : 0)) + (segmentToInsert.nodesOnSegment.First() == 0 ? 1 : 0);
                    Segment ok = new Segment();
                    for (int j = 0; j <= splittingAfterIndex; j++)
                    {
                        ok.Add(segmentToInsert.nodesOnSegment[j]);
                    }
                    segmentToInsert.RemoveNodesUpToAndIncluding(splittingAfterIndex);
                    InsertSegmentIntoCollection(ok, overlappingSegments);
                    InsertSegmentIntoCollection(segmentToInsert, overlappingSegments);
                }
                else
                {
                    overlappingSegments.Add(segmentToInsert);
                }
            }
        }

        private static void JoinSegments(List<Segment> overlappingSegments)
        {
            // Console.WriteLine("Entering routine of joining segments in a greedy way");
            bool mergeDone;
            do
            {
                mergeDone = false;


                // Look at segments in random order
                int n = overlappingSegments.Count;
                while (n > 1)
                {
                    n--;
                    int k = Program.rand.Next(n + 1);
                    Segment value = overlappingSegments[k];
                    overlappingSegments[k] = overlappingSegments[n];
                    overlappingSegments[n] = value;
                }

                for (int i = 0; i < overlappingSegments.Count; i++)
                {
                    int mergeType = -1;
                    int mergeAt = -1;
                    double bestMergeCost = double.MaxValue;
                    int indexOfSecondSegment = -1;

                    for (int j = i + 1; j < overlappingSegments.Count; j++)
                    {
                        int sumSideDepots = 0;
                        if (overlappingSegments[i].nodesOnSegment.First() == 0)
                            sumSideDepots++;
                        if (overlappingSegments[i].nodesOnSegment.Last() == 0)
                            sumSideDepots++;
                        if (overlappingSegments[j].nodesOnSegment.First() == 0)
                            sumSideDepots++;
                        if (overlappingSegments[j].nodesOnSegment.Last() == 0)
                            sumSideDepots++;

                        if (sumSideDepots < 3 && overlappingSegments[i].segmentDemand + overlappingSegments[j].segmentDemand < Program.vrpData.Capacity)
                        {
                            mergeDone = true;
                            if (overlappingSegments[i].nodesOnSegment.First() != 0 && overlappingSegments[j].nodesOnSegment.First() != 0 && bestMergeCost > Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), 0])
                            {
                                mergeType = 1;
                                bestMergeCost = Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), 0];
                                indexOfSecondSegment = j;
                            }
                            if (overlappingSegments[i].nodesOnSegment.First() != 0 && overlappingSegments[j].nodesOnSegment.Last() != 0 && bestMergeCost > Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), 0])
                            {
                                mergeType = 2;
                                bestMergeCost = Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), 0];
                                indexOfSecondSegment = j;
                            }
                            if (overlappingSegments[i].nodesOnSegment.Last() != 0 && overlappingSegments[j].nodesOnSegment.First() != 0 && bestMergeCost > Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), 0])
                            {
                                mergeType = 3;
                                bestMergeCost = Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.First()] - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), 0];
                                indexOfSecondSegment = j;
                            }
                            if (overlappingSegments[i].nodesOnSegment.Last() != 0 && overlappingSegments[j].nodesOnSegment.Last() != 0 && bestMergeCost > Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), 0])
                            {
                                mergeType = 4;
                                bestMergeCost = Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[0, overlappingSegments[j].nodesOnSegment.Last()] - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), 0];
                                indexOfSecondSegment = j;
                            }

                            // Might "merge" on the inside
                            if (overlappingSegments[i].nodesOnSegment.First() != 0 && overlappingSegments[i].nodesOnSegment.Last() != 0)
                            {
                                for (int k = 0; k < overlappingSegments[j].nodesOnSegment.Count(); k++)
                                {
                                    if (overlappingSegments[j].nodesOnSegment[k] == -1)
                                    {
                                        double mergeCost1 = Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment[k - 1]]
                                            + Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment[k + 1]]
                                            - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment[k - 1], overlappingSegments[j].nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), 0]
                                    - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), 0];
                                        double mergeCost2 = Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), overlappingSegments[j].nodesOnSegment[k + 1]]
                                            + Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), overlappingSegments[j].nodesOnSegment[k - 1]]
                                            - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment[k - 1], overlappingSegments[j].nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.Last(), 0]
                                    - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment.First(), 0];

                                        if (mergeCost1 < bestMergeCost)
                                        {
                                            mergeType = 5;
                                            mergeAt = k;
                                            bestMergeCost = mergeCost1;
                                            indexOfSecondSegment = j;
                                        }
                                        if (mergeCost2 < bestMergeCost)
                                        {
                                            mergeType = 6;
                                            mergeAt = k;
                                            bestMergeCost = mergeCost2;
                                            indexOfSecondSegment = j;
                                        }

                                    }
                                }
                            }


                            // Might "merge" on the inside
                            if (overlappingSegments[j].nodesOnSegment.First() != 0 && overlappingSegments[j].nodesOnSegment.Last() != 0)
                            {
                                for (int k = 0; k < overlappingSegments[i].nodesOnSegment.Count; k++)
                                {
                                    if (overlappingSegments[i].nodesOnSegment[k] == -1)
                                    {
                                        double mergeCost1 = Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.First(), overlappingSegments[i].nodesOnSegment[k - 1]]
                                            + Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.Last(), overlappingSegments[i].nodesOnSegment[k + 1]]
                                            - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment[k - 1], overlappingSegments[i].nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.Last(), 0]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.First(), 0];
                                        double mergeCost2 = Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.First(), overlappingSegments[i].nodesOnSegment[k + 1]]
                                            + Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.Last(), overlappingSegments[i].nodesOnSegment[k - 1]]
                                            - Program.vrpData.Distances[overlappingSegments[i].nodesOnSegment[k - 1], overlappingSegments[i].nodesOnSegment[k + 1]]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.Last(), 0]
                                    - Program.vrpData.Distances[overlappingSegments[j].nodesOnSegment.First(), 0];

                                        if (mergeCost1 < bestMergeCost)
                                        {
                                            mergeType = 7;
                                            mergeAt = k;
                                            bestMergeCost = mergeCost1;
                                            indexOfSecondSegment = j;
                                        }
                                        if (mergeCost2 < bestMergeCost)
                                        {
                                            mergeType = 8;
                                            mergeAt = k;
                                            bestMergeCost = mergeCost2;
                                            indexOfSecondSegment = j;
                                        }

                                    }
                                }
                            }

                        }
                    }
                    if (mergeDone == true)
                    {
                        // Actually merge
                        switch (mergeType)
                        {
                            case 1:
                                overlappingSegments[i].nodesOnSegment.Reverse();
                                overlappingSegments[i].Add(-1);
                                overlappingSegments[i].AddRange(overlappingSegments[indexOfSecondSegment]);
                                overlappingSegments.RemoveAt(indexOfSecondSegment);
                                break;
                            case 2:
                                overlappingSegments[indexOfSecondSegment].Add(-1);
                                overlappingSegments[indexOfSecondSegment].AddRange(overlappingSegments[i]);
                                overlappingSegments.RemoveAt(i);
                                break;
                            case 3:
                                overlappingSegments[i].Add(-1);
                                overlappingSegments[i].AddRange(overlappingSegments[indexOfSecondSegment]);
                                overlappingSegments.RemoveAt(indexOfSecondSegment);
                                break;
                            case 4:
                                overlappingSegments[i].nodesOnSegment.Reverse();
                                overlappingSegments[indexOfSecondSegment].Add(-1);
                                overlappingSegments[indexOfSecondSegment].AddRange(overlappingSegments[i]);
                                overlappingSegments.RemoveAt(i);
                                break;
                            case 5:
                                overlappingSegments[indexOfSecondSegment].Insert(mergeAt, -1);
                                overlappingSegments[indexOfSecondSegment].InsertRange(mergeAt + 1, overlappingSegments[i]);
                                overlappingSegments.RemoveAt(i);
                                break;
                            case 6:
                                overlappingSegments[i].nodesOnSegment.Reverse();
                                overlappingSegments[indexOfSecondSegment].Insert(mergeAt, -1);
                                overlappingSegments[indexOfSecondSegment].InsertRange(mergeAt + 1, overlappingSegments[i]);
                                overlappingSegments.RemoveAt(i);
                                break;
                            case 7:
                                overlappingSegments[i].Insert(mergeAt, -1);
                                overlappingSegments[i].InsertRange(mergeAt + 1, overlappingSegments[indexOfSecondSegment]);
                                overlappingSegments.RemoveAt(indexOfSecondSegment);
                                break;
                            case 8:
                                overlappingSegments[indexOfSecondSegment].nodesOnSegment.Reverse();
                                overlappingSegments[i].Insert(mergeAt, -1);
                                overlappingSegments[i].InsertRange(mergeAt + 1, overlappingSegments[indexOfSecondSegment]);
                                overlappingSegments.RemoveAt(indexOfSecondSegment);
                                break;
                        }

                        break;
                    }
                }

            } while (mergeDone == true);
        }

        private static List<Segment> FindOverlappingSegments(CVRPSolution cVRPSolution1, CVRPSolution cVRPSolution2, int[] overlappingIndicator)
        {
            List<Segment> overlappingSegments = new List<Segment>();

             for (int sol1RouteIndex = 0; sol1RouteIndex < cVRPSolution1.routesInSolution.Count; sol1RouteIndex++)
            {
                for (int sol2RouteIndex = 0; sol2RouteIndex < cVRPSolution2.routesInSolution.Count; sol2RouteIndex++)
                {
                    int sol1NodeIndex = 0;
                    while (sol1NodeIndex < cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment.Count - 1)
                    {
                        for (int sol2NodeIndex = 0; sol2NodeIndex < cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment.Count - 1; sol2NodeIndex++)
                        {
                            if (cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex] == cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment[sol2NodeIndex] && cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + 1] == cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment[sol2NodeIndex+1])
                            {
                                Segment currentSegment = new Segment();

                                currentSegment.Add(cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex ]);
                                currentSegment.Add(cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + 1]);

                                overlappingIndicator[cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex ]] = 1;
                                overlappingIndicator[cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + 1]] = 1;

                                int jj = 2;
                                while (sol1NodeIndex + jj < cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment.Count && sol2NodeIndex + jj < cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment.Count && cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + 1] == cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment[sol2NodeIndex + jj])
                                {
                                    currentSegment.Add(cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + jj]);
                                     overlappingIndicator[cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + jj]] = 1;
                                    jj++;
                                }
                                overlappingSegments.Add(currentSegment);
                                 sol1NodeIndex += jj - 1;
                                break;
                            }
                        }
                        sol1NodeIndex += 1;
                    }
                }
            }

        
            for (int sol1RouteIndex = 0; sol1RouteIndex < cVRPSolution1.routesInSolution.Count; sol1RouteIndex++)
            {
                for (int sol2RouteIndex = 0; sol2RouteIndex < cVRPSolution2.routesInSolution.Count; sol2RouteIndex++)
                {
                    int sol1NodeIndex = 0;
                    while (sol1NodeIndex < cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment.Count - 1)
                    {
                        for (int sol2NodeIndex = cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment.Count - 1; sol2NodeIndex > 0; sol2NodeIndex--)
                        {
                            if (cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex] == cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment[sol2NodeIndex ] && cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + 1] == cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment[sol2NodeIndex - 1]
                                && (overlappingIndicator[cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex]] == 0 || overlappingIndicator[cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex+1]] == 0))
                            {
                                Segment currentSegment = new Segment();
                                currentSegment.Add(cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex]);
                                currentSegment.Add(cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + 1]);

                           
                                overlappingIndicator[cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex]] = 1;
                                overlappingIndicator[cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex+1]] = 1;

                                int jj = 2;
                                while (sol1NodeIndex + jj < cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment.Count && sol2NodeIndex - jj < cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment.Count && cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + jj] == cVRPSolution2.routesInSolution[sol2RouteIndex].nodesOnSegment[sol2NodeIndex  - jj])
                                {
                                    currentSegment.Add(cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex + jj]);
                                       overlappingIndicator[cVRPSolution1.routesInSolution[sol1RouteIndex].nodesOnSegment[sol1NodeIndex+jj]] = 1;
                                    jj++;
                                }
                                overlappingSegments.Add(currentSegment);
                                sol1NodeIndex += jj - 1;
                                break;
                            }
                        }
                        sol1NodeIndex += 1;
                    }
                }
            }

            return overlappingSegments;
        }

        private static void CalculateNonOverlappingSegments(List<Segment> remainingSegments, int[] overlappingIndicator, CVRPSolution soln)
        {
            Segment currentShortSegment = new Segment();

            bool atTheBeginning = true;
            bool inAsegment = false;

            for (int routeIndex = 0; routeIndex < soln.routesInSolution.Count; routeIndex++)
            {
                // In this route, find segments which are not in the routeIndex
                for (int nodeIndex = 1; nodeIndex < soln.routesInSolution[routeIndex].nodesOnSegment.Count; nodeIndex++)
                {
                    // If it was not an overlapping member, we might add it to segments
                    if (overlappingIndicator[soln.routesInSolution[routeIndex].nodesOnSegment[nodeIndex]] == 0)
                    {
                        if (inAsegment == false)
                        {
                            if (soln.routesInSolution[routeIndex].nodesOnSegment[nodeIndex] == 0) break;
                            currentShortSegment = new Segment();
                            if (atTheBeginning)
                                currentShortSegment.Add(0);
                            currentShortSegment.Add(soln.routesInSolution[routeIndex].nodesOnSegment[nodeIndex]);
                            remainingSegments.Add(currentShortSegment);
                            inAsegment = true;
                        }
                        else
                            currentShortSegment.Add(soln.routesInSolution[routeIndex].nodesOnSegment[nodeIndex]);
                    }
                    else
                    {
                        inAsegment = false;
                        atTheBeginning = false;
                    }
                }
            }
        }
        
    }
}